package name.huzhenbo.java.algorithm.recursion;

class Fibonacci {

    /**
     * 线性递归：
     * 每次重复的过程
     * 调用都使得调用链条不断加长. 系统不得不使用栈进行数据保存和恢复。
     * 被调用的函数需要返回至调用它的函数那里。
     *
     * @param n
     * @return
     */
    public static int recur(int n) {
        if (n == 1) {
            return 1;
        }
        return n * recur(n - 1);
    }


    /**
     * 尾递归：
     * 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部,
     * 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者,
     * 返回到调用者的调用者去. And so on, just skip all recursive call, directly back to the root. 
     *
     * Tail recursive can be easily replaced by loop.
     *
     * @param n
     * @param initial
     * @return
     */
    public static int tailRecur(int n, int initial) {
        if (n == 1) {
            return initial;
        }
        return tailRecur(n - 1, n * initial);
    }
}
